package org.ala.tiktools.tools.list;

import java.util.Arrays;

/**
 * 定长循环队列
 * <p>  非线程安全
 * <p>  定长数组实现，不扩容
 * <p>	队列本身无gc压力，也不扩容。适用于对性能要求极高，的顺序读写，的场景
 *
 * @author ala
 * @date 2025-04-11 13:30
 */
public class FixedCircularList<E> {
    /**
     *  存放数据数组
     */
    protected E[] datas;
    /**
     *  当前数据长度
     */
    protected int size = 0;
    /**
     *  容量
     */
    protected int capacity;
    /**
     *  读针：指向当前可读下标
     *  <p> 只有 size > 0 时才有效
     */
    protected int readerIndex = 0;
    /**
     *  写针：指向下一个可写下标
     */
    protected int writerIndex = 0;


    /**
     * 用空数组初始化
     */
    public FixedCircularList(E[] arr) {
        this.capacity = arr.length;
        this.datas = arr;
        this.size = 0;
    }
    /**
     * 直接指定读写针
     */
    public FixedCircularList(E[] arr, int readerIndex, int writerIndex) {
    	this.capacity = arr.length;
    	this.datas = arr;
    	this.size = writerIndex > readerIndex ? writerIndex - readerIndex : capacity - readerIndex + writerIndex - 1;
    	this.readerIndex = readerIndex;
    	this.writerIndex = writerIndex;
    }


    public boolean isEmpty() {
        return size == 0;
    }
    public boolean isFull() {
        return size == capacity;
    }
    /**
     * 可读长度
     */
    public int size() {
        return size;
    }
    /**
     *  剩余可写长度
     */
    public int writeableLength() {
        return capacity - size;
    }


    /**
     *  取第i个数据（从0开始）
     */
	public E indexOf(int i) {
        int p = (readerIndex + i) % capacity;
        if (p >= writerIndex) {return null;}
        return datas[p];
    }
	/**
     *  取第i个数据（从0开始）
     */
	public E unsafeIndexOf(int i) {
        return datas[i];
    }
	/**
	 * 	删除第一个
	 */
	public void removeFirst() {
		datas[readerIndex] = null;
		if (++readerIndex == capacity) { readerIndex = 0; }
		size--;
	}
    
    /**
     *  offer / add 数据
     *  @return -1:容量已满 | 1:成功
     */
    public boolean offer(E e) {
        if (size == capacity) {
            return false;
        }
        datas[writerIndex++] = e;
        if (writerIndex == capacity) {
            writerIndex = 0;
        }
        size++;
        return true;
    }
    /**
     *  peek
     */
    public E peek() { 
    	if (size == 0) { return null; }
    	return indexOf(readerIndex); 
    }
    /**
     *  pop
     */
	public E pop() {
        if (size == 0) {return null;}
        E r = (E) datas[readerIndex];
        //  不再持有引用
        datas[readerIndex] = null;
        if (++readerIndex == capacity) {
            readerIndex = 0;
        }
        size--;
        return r;
    }
    
    
    /**
     * 	删除p位置（p只能在可读范围内）
     * 	<p>	如果是[---r--p--w---]这样的情况：
     * 	<p>		如果p离r更近，把p抽走，把[r, p)内的数右移，r右移一次
     * 	<p>		如果p离w更新，把p抽走，把(p, w)内的数左移，w左移一次
     * 	<p>	如果是[-p-w-----r--]这样的情况：
     *  <p>		如果p在[0,w]范围内，把p抽走，把(p,w)内的数左移，w左移一次
     *  <p>		如果p在[r,N)范围内，把p抽走，把(r,p)内的数右移，r右移一次
     *  <p>	如果是：[------------] size == 0
     *  <p>		   [-p--r---w-p-] p在可写范围之外
     *  <p>		   [--w--p---r--] p在可写范围之外
     *  <p>	这些情况不合法，直接返回
     *  @return false:插入失败 | true:插入成功
     */
    public boolean remove(int p) {
    	//	数组为空，没得挪
    	if (size == 0 || p < 0 || p >= capacity) { return false; }
    	int r = readerIndex, w = writerIndex;
    	//	[---r----w--]的情况
    	if (r < w) {
    		//	p在可写范围之外
    		if (p < r || p >= w) { return false; }
    		int dr = p-r, dw = w-1-p;
    		//	离r更近
    		if (dr < dw) {
    			for (int i = p ; i > r ; i--) { swap(i, i-1); }
    			readerIndex++;
    			datas[r] = null;
    		} 
    		//	离w更近
    		else {
    			for (int i = p ; i < w-1 ; i++) { swap(i, i+1); }
    			writerIndex--;
    			datas[w-1] = null;
    		}
    	}
    	//	[---w----r--]的情况
    	else {
    		//	p在可写范围之外
    		if (p >= w && p < r) { return false; }
    		//	离r更近
    		if (p >= r) {
    			for (int i = p ; i > r ; i--) { swap(i, i-1); }
    			if (++readerIndex == capacity) {readerIndex = 0;}
    			datas[r] = null;
    		}
    		//	离w更近
    		else if (p < w) {
    			for (int i = p ; i < w-1 ; i++) { swap(i, i+1); }
    			if (--writerIndex == -1) {writerIndex = capacity - 1;}
    			datas[w-1] = null;
    		}
    	}
    	size--;
    	return true;
    }
    /**
     * 	在p的位置插入数据（p只能在可读范围内）
     * 	<p>	如果是[---r------w---]这样的情况
     * 	<p>		如果p离r更近，在p的位置插入，r左移
     * 	<p>		如果p离w更近，在p的位置插入，w右移
     * 	<p>	如果是[---w------r---]这样的情况
     *  <p>		如果p离r更近，在p的位置插入，r左移
     *  <p>		如果p离w更近，在p的位置插入，w右移
     *  @return	false:失败 | true:成功
     */
    public boolean insert(int p, E o) {
    	if (size == 0 || p < 0 || p >= capacity) { return false; }
    	int r = readerIndex, w = writerIndex;
    	//	如果是[---r------w---]这样的情况
    	if (r < w) {
    		if (p < r || p >= w) {return false;}
    		int dr = p - r, dw = w-1 - p;
    		if (dr < dw) {
    			for (int i = r-1 ; i < p ; i++) {
    				int _i = i;
    				if (_i < 0) {_i = capacity - 1;}
    				swap(_i, _i+1);
    			}
    			datas[p] = o;
    			if (--readerIndex < 0) {readerIndex = capacity-1;}
    		} else {
    			for (int i = w ; i > p ; i--) {
    				swap(i, i-1);
    			}
    			datas[p] = o;
    			if (++writerIndex == capacity) { writerIndex = 0; }
    		}
    	} 
    	//	如果是[---w------r---]这样的情况
    	else {
    		if (p < r && p >= w) { return false; }
    		if (p >= r) {
    			for (int i = r-1 ; i < p ; i++) {
    				swap(i, i+1);
    			}
    			datas[p] = o;
    			--readerIndex;
    		} else if (p < w) {
    			for (int i = w ; i > p ; i--) {
    				swap(i, i-1);
    			}
    			datas[p] = o;
    			++writerIndex;
    		}
    	}
    	size++;
    	return true;
    }
    /**
     * 	交换两个下标的内容
     */
    public void swap(int i, int j) {
    	E t = datas[i];
    	datas[i] = datas[j];
    	datas[j] = t;
    }
    
	@Override
	public String toString() {
		return String.format("%s, r:%d, w:%d", Arrays.toString(datas), readerIndex, writerIndex);
	}
}
